package csp;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CSP<V,D> {
	
	private List<V> variables;//变量
	private Map<V,List<D>> domains;//值域
	private Map<V,List<Constraint<V,D>>> constraints = new HashMap<>();//约束

	public CSP(List<V> variables,Map<V,List<D>> domains) {
		this.variables = variables;
		this.domains = domains;
	}

	//建立变量与约束的对应关系
	public void addConstraint(Constraint<V,D> constraint) {
		for(V variable:constraint.getVariables()) {
			List<Constraint<V,D>> list = constraints.get(variable);
			if(list==null) {
				list = new ArrayList<Constraint<V,D>>();
			}
			list.add(constraint);
			constraints.put(variable,list);
		}
	}
	
	public Map<V, D> backtrackingSearch(Map<V, D> assignment) {
		if (assignment.size() == variables.size()) {
			return assignment;
		}
		//比如variables永久为A、B、C、D、E，assignment为A、B，那么待处理的就是C
		V unassigned = variables.stream().filter(v->!assignment.containsKey(v)).findFirst().get();
		for (D value:domains.get(unassigned)) {
			Map<V,D> localAssignment = new HashMap<>(assignment);
			localAssignment.put(unassigned,value);
			if (consistent(unassigned,localAssignment)) {
				Map<V,D> result = backtrackingSearch(localAssignment);
				if (result != null) {
					return result;
				}
			}
		}
		return null;
	}
	
	public boolean consistent(V variable,Map<V,D> assignment) {
		for (Constraint<V,D> constraint:constraints.get(variable)) {
			if (!constraint.satisfied(assignment)) {
				return false;
			}
		}
		return true;
	}
	
}
